#pragma once
#include<iostream>
#include<vector>



class UnionFindSet
{
public:
	UnionFindSet(int size)
		:_set(size,-1)
	{}

	//查找元素是否在集合里
	//size_t FindRoot(int x)
	//{
	//	while (_set[x] >= 0)
	//	{
	//		x = _set[x];
	//	}
	//	return x;
	//}

	size_t FindRoot(int x)
	{
		//找根
		size_t root = x;
		while (_set[x] >= 0)
		{
			x = _set[x];
		}

		//压缩
		while (_set[x] >= 0)
		{
			size_t parent = _set[x];
			_set[x] = root;

			x = parent;
		}
		return root;

	}

	//合并
	void Union(int x1, int x2)
	{
		int root1 = FindRoot(x1);
		int root2 = FindRoot(x2);
		if (root1 != root2)
		{
			_set[root1] += _set[root2];
			_set[root2] = root1;	
		}
	}

	//集合个数
	size_t SetCount()
	{
		size_t count = 0;
		for (auto x : _set)
		{
			if (x < 0)
				count++;
		}
	}

private:
	std::vector<int> _set;
};


